

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=auto>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/favicon.png">
  <link rel="icon" href="/img/favicon.png">
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=5.0, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="author" content="Cai Shibo">
  <meta name="keywords" content="cc">
  
    <meta name="description" content="该文章记录对 排序 相关题目的分析理解。">
<meta property="og:type" content="article">
<meta property="og:title" content="算法---排序">
<meta property="og:url" content="https://hahsx_xd.gitee.io/2022/03/24/%E7%AE%97%E6%B3%95--%E6%8E%92%E5%BA%8F/index.html">
<meta property="og:site_name" content="🍊CAI SHIBO🥬">
<meta property="og:description" content="该文章记录对 排序 相关题目的分析理解。">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://hahsx_xd.gitee.io/images/pasted-65.png">
<meta property="og:image" content="https://hahsx_xd.gitee.io/images/pasted-66.png">
<meta property="article:published_time" content="2022-03-24T12:36:00.000Z">
<meta property="article:modified_time" content="2022-11-29T07:14:46.511Z">
<meta property="article:author" content="Cai Shibo">
<meta property="article:tag" content="排序">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="https://hahsx_xd.gitee.io/images/pasted-65.png">
  
  
  <title>算法---排序 - 🍊CAI SHIBO🥬</title>

  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bootstrap@4/dist/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/github-markdown-css@4/github-markdown.min.css" />
  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/hint.css@2/hint.min.css" />

  
    
    
      
      <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/highlight.js@10/styles/github-gist.min.css" />
    
  

  
    <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3/dist/jquery.fancybox.min.css" />
  


<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_ba1fz6golrf.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_lbnruvf0jn.css">


<link  rel="stylesheet" href="/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script id="fluid-configs">
    var Fluid = window.Fluid || {};
    var CONFIG = {"hostname":"hahsx_xd.gitee.io","root":"/","version":"1.8.14","typing":{"enable":true,"typeSpeed":70,"cursorChar":".|","loop":false},"anchorjs":{"enable":true,"element":"h1,h2,h3,h4,h5,h6","placement":"right","visible":"hover","icon":"#"},"progressbar":{"enable":true,"height_px":3,"color":"#29d","options":{"showSpinner":false,"trickleSpeed":100}},"copy_btn":true,"image_zoom":{"enable":true,"img_url_replace":["",""]},"toc":{"enable":true,"headingSelector":"h1,h2,h3,h4,h5,h6","collapseDepth":5},"lazyload":{"enable":true,"loading_img":"/img/loading.gif","onlypost":true,"offset_factor":2},"web_analytics":{"enable":false,"baidu":null,"google":null,"gtag":null,"tencent":{"sid":null,"cid":null},"woyaola":null,"cnzz":null,"leancloud":{"app_id":null,"app_key":null,"server_url":null,"path":"window.location.pathname","ignore_local":false}},"search_path":"/local-search.xml"};
  </script>
  <script  src="/js/utils.js" ></script>
  <script  src="/js/color-schema.js" ></script>
<meta name="generator" content="Hexo 5.4.0"><link rel="alternate" href="/atom.xml" title="🍊CAI SHIBO🥬" type="application/atom+xml">
</head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand" href="/">
      <strong>^_^ 🥬 CC</strong>
    </a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/tags/">
                <i class="iconfont icon-tags-fill"></i>
                标签
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" target="_self" href="javascript:;" data-toggle="modal" data-target="#modalSearch" aria-label="Search">
              &nbsp;<i class="iconfont icon-search"></i>&nbsp;
            </a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" target="_self" href="javascript:;" aria-label="Color Toggle">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner" id="banner" parallax=true
         style="background: url('/img/default.png') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="page-header text-center fade-in-up">
            <span class="h2" id="subtitle" title="算法---排序">
              
            </span>

            
              <div class="mt-3">
  
    <span class="post-meta mr-2">
      <i class="iconfont icon-author" aria-hidden="true"></i>
      Cai Shibo
    </span>
  
  
    <span class="post-meta">
      <i class="iconfont icon-date-fill" aria-hidden="true"></i>
      <time datetime="2022-03-24 20:36" pubdate>
        2022年3月24日 晚上
      </time>
    </span>
  
</div>

<div class="mt-1">
  
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      12k 字
    </span>
  

  
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      59 分钟
    </span>
  

  
  
    
      <!-- 不蒜子统计文章PV -->
      <span id="busuanzi_container_page_pv" style="display: none">
        <i class="iconfont icon-eye" aria-hidden="true"></i>
        <span id="busuanzi_value_page_pv"></span> 次
      </span>
    
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid nopadding-x">
  <div class="row nomargin-x">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-x-md">
      <div class="container nopadding-x-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto">
            <!-- SEO header -->
            <h1 style="display: none">算法---排序</h1>
            
              <p class="note note-info">
                
                  最后更新：23 天前
                
              </p>
            
            <div class="markdown-body">
              <p><strong>该文章记录对 排序 相关题目的分析理解。</strong></p>
<span id="more"></span>

<hr>
<h3 id="十大排序算法"><a href="#十大排序算法" class="headerlink" title="十大排序算法"></a>十大排序算法</h3><p><img src="/images/pasted-65.png" srcset="/img/loading.gif" lazyload alt="排序算法概述"></p>
<hr>
<h4 id="1-冒泡排序"><a href="#1-冒泡排序" class="headerlink" title="1.冒泡排序"></a>1.冒泡排序</h4><ol>
<li>比较相邻的元素。如果第一个比第二个大，就交换他们两个。</li>
<li>对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。</li>
<li>针对所有的元素重复以上的步骤，除了最后一个。</li>
<li>持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。</li>
</ol>
<p><strong>优化：</strong>使用一个boolean记录此次冒泡排序是否进行过交换，如果没有进行交换，说明当前已是有序序列，不用再排序。<br>每进行一次冒泡，无序序列中的最大值一定会被放到最后，那么最后已经确定最大的值就无须参与排序，避免重复比较。</p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">// 总共要经过 N-1 轮比较</span><br><span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt; arr.length; i++) &#123;<br>	<span class="hljs-comment">//若为true则表示此次循环没有进行交换，待排序列已有序，排序已经完成</span><br>    <span class="hljs-keyword">boolean</span> flag = <span class="hljs-keyword">true</span>;<br>    <span class="hljs-comment">// 每轮需要比较的次数 N-i</span><br>    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; arr.length - i; j++) &#123;<br>         <span class="hljs-keyword">if</span> (arr[j] &gt; arr[j + <span class="hljs-number">1</span>]) &#123;<br>              <span class="hljs-keyword">int</span> tmp = arr[j];<br>              arr[j] = arr[j + <span class="hljs-number">1</span>];<br>              arr[j + <span class="hljs-number">1</span>] = tmp;<br>              flag = <span class="hljs-keyword">false</span>;<br>          &#125;<br>     &#125;<br>     <span class="hljs-keyword">if</span> (flag) &#123;<br>          <span class="hljs-keyword">break</span>;<br>     &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<hr>
<h4 id="2-选择排序"><a href="#2-选择排序" class="headerlink" title="2.选择排序"></a>2.选择排序</h4><ol>
<li>首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。</li>
<li>再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。</li>
<li>重复第二步，直到所有元素均排序完毕。</li>
</ol>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">// 总共要经过 N-1 轮比较</span><br><span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; arr.length - <span class="hljs-number">1</span>; i++) &#123;<br>    <span class="hljs-keyword">int</span> min_index = i;<br>    <span class="hljs-comment">// 每轮需要比较的次数 N-i</span><br>    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = i + <span class="hljs-number">1</span>; j &lt; arr.length; j++) &#123;<br>        <span class="hljs-keyword">if</span> (arr[j] &lt; arr[min_index]) &#123;<br>            <span class="hljs-comment">// 记录目前能找到的最小值元素的下标</span><br>            min_index = j;<br>        &#125;<br>    &#125;<br>    <span class="hljs-comment">// 将找到的最小值和i位置所在的值进行交换</span><br>    <span class="hljs-keyword">if</span> (i != min) &#123;<br>        <span class="hljs-keyword">int</span> tmp = arr[i];<br>        arr[i] = arr[min_index];<br>        arr[min_index] = tmp;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>

<hr>
<h4 id="3-插入排序"><a href="#3-插入排序" class="headerlink" title="3.插入排序"></a>3.插入排序</h4><ol>
<li>将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。</li>
<li>从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果<strong>待插入的元素与有序序列中的某个元素相等</strong>，则<strong>将待插入元素插入到相等元素的后面</strong>。）</li>
</ol>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">// 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的</span><br><span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt; arr.length; i++) &#123;<br>    <span class="hljs-comment">// 记录要插入的数据</span><br>    <span class="hljs-keyword">int</span> tmp = arr[i];<br>    <span class="hljs-comment">// 从已经排序的序列最右边的开始比较，找到比其小的数</span><br>    <span class="hljs-keyword">int</span> j = i;<br>    <span class="hljs-keyword">while</span> (j &gt; <span class="hljs-number">0</span> &amp;&amp; tmp &lt; arr[j - <span class="hljs-number">1</span>]) &#123;<br>        arr[j] = arr[j - <span class="hljs-number">1</span>];<br>        j--;<br>    &#125;<br>    <span class="hljs-comment">// 存在比其小的数，插入</span><br>    <span class="hljs-keyword">if</span> (j != i) &#123;<br>        arr[j] = tmp;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>

<p><strong>优化，折半插入：</strong>折半插入排序其实是在直接插入排序的基础上，结合了二分查找法的思想，顺序的二分查找替代了直接插入排序中遍历查找的过程，从而更快的能够确定待插入元素的位置，但是由于移动次数并没有发生改变，所以两者的时间复杂度相同。折半插入排序是稳定的，其时间复杂度为O(N^2)。</p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">int</span> temp;<br><span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt; array.length; i++) &#123;<br>    <span class="hljs-keyword">int</span> low = <span class="hljs-number">0</span>;<br>    <span class="hljs-keyword">int</span> hight = i - <span class="hljs-number">1</span>;<br>    temp = array[i];<br>    <span class="hljs-keyword">while</span> (hight &gt;= low) &#123;<br>        <span class="hljs-keyword">int</span> mid = ( low + hight ) / <span class="hljs-number">2</span>;<br>        <span class="hljs-keyword">if</span> (array[mid] &gt; temp) &#123;<br>            hight = mid - <span class="hljs-number">1</span>;<br>        &#125; <span class="hljs-keyword">else</span> &#123;<br>            low = mid + <span class="hljs-number">1</span>;<br>        &#125;<br>    &#125;<br>    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = i - <span class="hljs-number">1</span>; j &gt; hight; j--) &#123;<br>        array[j + <span class="hljs-number">1</span>] = array[j];<br>    &#125;<br>    array[hight + <span class="hljs-number">1</span>] = temp;<br>&#125;<br></code></pre></div></td></tr></table></figure>

<hr>
<h4 id="4-希尔排序"><a href="#4-希尔排序" class="headerlink" title="4.希尔排序"></a>4.希尔排序</h4><p>希尔排序(Shell Sort)是插入排序的一种算法，是<strong>对直接插入排序的优化</strong>，也称缩小增量排序。<br>希尔排序是基于直接插入排序的以下两点性质而提出的改进方法：</p>
<ol>
<li>插入排序在对几乎已经排好序的数据操作时效率高，可<strong>达到线性排序的效率</strong>。</li>
<li>插入排序一般来说是低效的，因为插入排序<strong>每次只能将数据移动一位</strong>。</li>
</ol>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">//希尔排序  升序</span><br><span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> d = arr.length / <span class="hljs-number">2</span>; d &gt; <span class="hljs-number">0</span>; d /= <span class="hljs-number">2</span>) &#123; <span class="hljs-comment">//d：增量</span><br>    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = d; i &lt; arr.length; i++) &#123;<br>    <br>        <span class="hljs-comment">//此处用for循环是防止交换到前面的值小于再前面的值</span><br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = i - d; j &gt;= <span class="hljs-number">0</span>; j -= d) &#123; <br>        <span class="hljs-comment">//在此处-d 为了避免下面数组角标越界</span><br>            <span class="hljs-keyword">if</span> (arr[j] &gt; arr[j + d]) &#123;<span class="hljs-comment">// j+d 代表即将插入的元素所在的角标</span><br>                <span class="hljs-comment">//符合条件，插入元素（交换位置）</span><br>                <span class="hljs-keyword">int</span> temp = arr[j];<br>                arr[j] = arr[j + d];<br>                arr[j + d] = temp;<br>            &#125;<br>            <span class="hljs-keyword">else</span> &#123;<br>            <span class="hljs-comment">//如果没有进行交换，可以直接跳出当前for</span><br>            	<span class="hljs-keyword">break</span>;<br>            &#125;<br>        &#125;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>

<hr>
<h4 id="5-归并排序"><a href="#5-归并排序" class="headerlink" title="5.归并排序"></a>5.归并排序</h4><p>归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用<strong>分治法（Divide and Conquer）</strong>的一个非常典型的应用。<br>作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：<br>自上而下的递归（所有递归的方法都可以用迭代重写，因此也有了第 2 种方法）；自下而上的迭代。</p>
<ol>
<li>申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；</li>
<li>设定两个指针，最初位置分别为两个已经排序序列的起始位置；</li>
<li>比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；</li>
<li>重复步骤 3 直到某一指针达到序列尾；</li>
<li>将另一序列剩下的所有元素直接复制到合并序列尾。</li>
</ol>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">MergeSort</span> </span>&#123;<br>    <span class="hljs-comment">//用于暂存当前两个子集合的排序结果，外部new节省了之后merge()中new浪费的空间</span><br>    <span class="hljs-keyword">static</span> <span class="hljs-keyword">int</span>[] temp;<br><br>	<span class="hljs-comment">//分治过程</span><br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">sort</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] arr, <span class="hljs-keyword">int</span> left, <span class="hljs-keyword">int</span> right)</span> </span>&#123;<br>        <span class="hljs-keyword">if</span> (left &lt; right) &#123;<br>            <span class="hljs-keyword">int</span> mid = (left + right) / <span class="hljs-number">2</span>;<br>            sort(arr, left, mid);<br>            sort(arr, mid + <span class="hljs-number">1</span>, right);<br>            merge(arr, left, mid, right);<br>        &#125;<br>    &#125;<br><br>	<span class="hljs-comment">//归并过程</span><br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">merge</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] arr, <span class="hljs-keyword">int</span> left, <span class="hljs-keyword">int</span> mid, <span class="hljs-keyword">int</span> right)</span> </span>&#123;<br>        <span class="hljs-keyword">int</span> index = <span class="hljs-number">0</span>;<br>        <span class="hljs-keyword">int</span> i = left, j = mid + <span class="hljs-number">1</span>;<br>        <span class="hljs-keyword">while</span> (i &lt;= mid &amp;&amp; j &lt;= right) &#123;<br>            <span class="hljs-comment">//加&#x27;=&#x27;保持排序稳定性</span><br>            <span class="hljs-keyword">if</span> (arr[i] &lt;= arr[j]) &#123;<br>                temp[index++] = arr[i++];<br>            &#125;<br>            <span class="hljs-keyword">else</span> &#123;<br>                temp[index++] = arr[j++];<br>            &#125;<br>        &#125;<br>        <span class="hljs-comment">//左序列还有剩余</span><br>        <span class="hljs-keyword">while</span> (i &lt;= mid) &#123;<br>            temp[index++] = arr[i++];<br>        &#125;<br>        <span class="hljs-keyword">while</span> (j &lt;= right) &#123;<br>            temp[index++] = arr[j++];<br>        &#125;<br><br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> k = <span class="hljs-number">0</span>; k &lt; index ; ++k) &#123;<br>            arr[left + k] = temp[k];<br>        &#125;<br>    &#125;<br><br>	<span class="hljs-comment">//main()</span><br>	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;<br>        <span class="hljs-keyword">int</span>[] arr = &#123;<span class="hljs-number">11</span>,<span class="hljs-number">44</span>,<span class="hljs-number">23</span>,<span class="hljs-number">67</span>,<span class="hljs-number">88</span>,<span class="hljs-number">65</span>,<span class="hljs-number">34</span>,<span class="hljs-number">48</span>,<span class="hljs-number">9</span>,<span class="hljs-number">12</span>&#125;;<br>        temp = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[arr.length];<br>        sort(arr, <span class="hljs-number">0</span>, arr.length - <span class="hljs-number">1</span>);<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;arr.length;i++)&#123;<br>            System.out.print(arr[i]+<span class="hljs-string">&quot; &quot;</span>);<br>        &#125;<br>    &#125;<br>&#125;<br><br></code></pre></div></td></tr></table></figure>

<hr>
<h4 id="6-快速排序"><a href="#6-快速排序" class="headerlink" title="6.快速排序"></a>6.快速排序</h4><p>快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。<br>快速排序使用<strong>分治法（Divide and conquer）</strong>策略来把一个串行（list）分为两个子串行（sub-lists）。<br>快速排序又是一种<strong>分而治之思想</strong>在排序算法上的典型应用。本质上来看，快速排序应该算是在<strong>冒泡排序基础上的递归分治法</strong>。</p>
<ol>
<li>从数列中挑出一个元素，称为 “基准”（pivot）;</li>
<li>重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；</li>
<li>递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；</li>
</ol>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">QuickSort</span> </span>&#123;<br>    <span class="hljs-comment">//将当前数组分区，并对两个分区进行递归</span><br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">sort</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] arr, <span class="hljs-keyword">int</span> left, <span class="hljs-keyword">int</span> right)</span> </span>&#123;<br>        <span class="hljs-keyword">if</span> (left &lt; right) &#123;<br>            <span class="hljs-keyword">int</span> mid = partition(arr, left, right);<br>            <span class="hljs-comment">//mid已经在正确的位置了，不再参与排序！</span><br>            sort(arr, left, mid - <span class="hljs-number">1</span>);<br>            sort(arr, mid + <span class="hljs-number">1</span>, right);<br>        &#125;<br>        <span class="hljs-keyword">return</span>;<br>    &#125;<br><br>    <span class="hljs-comment">//将数组以基准值分区</span><br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">int</span> <span class="hljs-title">partition</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] arr, <span class="hljs-keyword">int</span> left, <span class="hljs-keyword">int</span> right)</span> </span>&#123;<br>        <span class="hljs-comment">//pivot为基准值，将序列元素以小于、大于arr[mid]分为左右两区</span><br>        <span class="hljs-keyword">int</span> pivot = arr[left];<br>        <span class="hljs-keyword">while</span> (left &lt; right) &#123;<br>            <span class="hljs-keyword">while</span> (left &lt; right &amp;&amp; arr[right] &gt;= pivot) &#123;<br>                right--;<br>            &#125;<br>            <span class="hljs-keyword">if</span> (left &lt; right) &#123;<br>                <span class="hljs-keyword">int</span> temp = arr[left];<br>                arr[left] = arr[right];<br>                arr[right] = temp;<br>            &#125;<br>            <span class="hljs-keyword">while</span> (left &lt; right &amp;&amp; arr[left] &lt;= pivot) &#123;<br>                left++;<br>            &#125;<br>            <span class="hljs-keyword">if</span> (left &lt; right) &#123;<br>                <span class="hljs-keyword">int</span> temp = arr[left];<br>                arr[left] = arr[right];<br>                arr[right] = temp;<br>            &#125;<br>        &#125;<br>        arr[left] = pivot;<br>        <span class="hljs-keyword">return</span> left;<br>    &#125;<br>    <br>    	<span class="hljs-comment">//main()</span><br>        <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;<br>        <span class="hljs-keyword">int</span>[] arr = &#123;<span class="hljs-number">11</span>, <span class="hljs-number">44</span>, <span class="hljs-number">23</span>, <span class="hljs-number">67</span>, <span class="hljs-number">88</span>, <span class="hljs-number">65</span>, <span class="hljs-number">34</span>, <span class="hljs-number">48</span>, <span class="hljs-number">9</span>, <span class="hljs-number">12</span>&#125;;<br>        sort(arr, <span class="hljs-number">0</span>, arr.length - <span class="hljs-number">1</span>);<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; arr.length; i++) &#123;<br>            System.out.print(arr[i] + <span class="hljs-string">&quot; &quot;</span>);<br>        &#125;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>

<hr>
<h4 id="7-堆排序"><a href="#7-堆排序" class="headerlink" title="7.堆排序"></a>7.堆排序</h4><p>堆排序（Heapsort）是指<strong>利用堆这种数据结构所设计</strong>的一种排序算法。<strong>堆积</strong>是一个<strong>近似完全二叉树的结构</strong>，并同时满足堆积的性质：即<strong>子结点的键值或索引总是小于（或者大于）它的父节点</strong>。<br>堆排序可以说是一种利用堆的概念来排序的<strong>选择排序</strong>。<br>分为两种方法：</p>
<ol>
<li>大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中<strong>用于升序排列</strong>；</li>
<li>小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中<strong>用于降序排列</strong>。</li>
</ol>
<div class="hljs code-wrapper"><pre><code class="hljs">为什么大顶堆适合升序，小顶堆适合降序？
解：大顶堆根结点值最大，将其与末尾节点位置交换后进行再堆调整，此时最大的根结点就在末尾节点。如此循环，越后面的节点就越大，整个数组自然就是升序。小顶堆适合降序同理。
</code></pre></div>
<p>算法步骤：</p>
<ol>
<li>创建一个堆 H[0……n-1]；</li>
<li>把堆首（最大值）和堆尾互换；</li>
<li>把堆的尺寸缩小 1，并调用 adjust(arr, index)，目的是把新的数组顶端数据调整到相应位置；</li>
<li>重复步骤 2，直到堆的尺寸为 1。</li>
</ol>
<div class="hljs code-wrapper"><pre><code class="hljs">大顶堆：arr[i] &gt;= arr[2i+1] &amp;&amp; arr[i] &gt;= arr[2i+2]；  
小顶堆：arr[i] &lt;= arr[2i+1] &amp;&amp; arr[i] &lt;= arr[2i+2]；  
第一个非叶子结点下标：arr.length/2-1。
</code></pre></div>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">HeapSort</span> </span>&#123;<br><br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">createHeap</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] arr)</span> </span>&#123;<br>        <span class="hljs-comment">//arr.length / 2 - 1 最后一个非叶子节点的下标，注意要-1</span><br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = arr.length / <span class="hljs-number">2</span> - <span class="hljs-number">1</span>; i &gt;= <span class="hljs-number">0</span>; --i) &#123;<br>            <span class="hljs-comment">//每个非叶子节点都需要按照大/小顶堆的概念检查、调整</span><br>            adjustHeap(arr, i, arr.length);<br>        &#125;<br>    &#125;<br>    <br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">adjustHeap</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] arr, <span class="hljs-keyword">int</span> root, <span class="hljs-keyword">int</span> length)</span> </span>&#123;<br>        <span class="hljs-comment">//得到下标root为根的左右子节点下标</span><br>        <span class="hljs-keyword">int</span> left = root * <span class="hljs-number">2</span> + <span class="hljs-number">1</span>, right = root * <span class="hljs-number">2</span> + <span class="hljs-number">2</span>;<br>        <span class="hljs-comment">//如果没有左子节点，说明当前节点为叶子节点</span><br>        <span class="hljs-keyword">if</span> (left &gt; length - <span class="hljs-number">1</span>) &#123;<br>            <span class="hljs-keyword">return</span>;<br>        &#125;<br><br>        <span class="hljs-keyword">int</span> index = root;<br>        <span class="hljs-comment">//判断左节点值是否大于根结点</span><br>        <span class="hljs-keyword">if</span> (arr[left] &gt; arr[index]) &#123;<br>            index = left;<br>        &#125;<br>        <span class="hljs-keyword">if</span> (right &lt; length &amp;&amp; arr[right] &gt; arr[index]) &#123;<br>            index = right;<br>        &#125;<br>        <span class="hljs-keyword">if</span> (root != index) &#123;<br>            <span class="hljs-keyword">int</span> temp = arr[root];<br>            arr[root] = arr[index];<br>            arr[index] = temp;<br>            <span class="hljs-comment">//调整了节点顺序，需要对调整后的子节点再进行检查、调整</span><br>            adjustHeap(arr, index, length);<br>        &#125;<br>    &#125;<br><br>	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;<br>        <span class="hljs-keyword">int</span>[] arr = &#123;<span class="hljs-number">11</span>, <span class="hljs-number">44</span>, <span class="hljs-number">23</span>, <span class="hljs-number">67</span>, <span class="hljs-number">88</span>, <span class="hljs-number">65</span>, <span class="hljs-number">34</span>, <span class="hljs-number">48</span>, <span class="hljs-number">9</span>, <span class="hljs-number">12</span>&#125;;<br>        <span class="hljs-comment">//创建大顶堆</span><br>        createHeap(arr);<br>        <span class="hljs-comment">//将堆顶与堆尾互换，断开堆尾（已是最大值），并对剩下的堆进行调整</span><br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; arr.length; ++i) &#123;<br>            <span class="hljs-keyword">int</span> temp = arr[<span class="hljs-number">0</span>];<br>            arr[<span class="hljs-number">0</span>] = arr[arr.length - i - <span class="hljs-number">1</span>];<br>            arr[arr.length - i - <span class="hljs-number">1</span>] = temp;<br>            <span class="hljs-comment">//堆顶堆尾交换后，断开堆尾，不再参与调整，所以每次长度-1</span><br>            adjustHeap(arr, <span class="hljs-number">0</span>, arr.length - i);<br>        &#125;<br><br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; arr.length; i++) &#123;<br>            System.out.print(arr[i] + <span class="hljs-string">&quot; &quot;</span>);<br>        &#125;<br>    &#125;<br><br>&#125;<br></code></pre></div></td></tr></table></figure>

<hr>
<h4 id="8-计数排序"><a href="#8-计数排序" class="headerlink" title="8.计数排序"></a>8.计数排序</h4><p>计数排序的核心在于<strong>将输入的数据值转化为键，存储在额外开辟的数组空间中</strong>。作为一种线性时间复杂度的排序，计数排序要求输入的数据<strong>必须是有确定范围的整数</strong>。计数排序不是比较排序，排序的速度快于任何比较排序算法。但是对于数据范围很大的数组，其需要大量时间和内存。</p>
<ol>
<li>找出待排序的数组中最大和最小的元素</li>
<li>统计数组中每个值为i的元素出现的次数，存入数组C的第i项</li>
<li>对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）</li>
<li>反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1</li>
</ol>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">CountingSort</span> </span>&#123;<br><br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">countingSort</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] arr, <span class="hljs-keyword">int</span> maxValue)</span> </span>&#123;<br>        <span class="hljs-comment">//数组的容量等于最大值+1，下标表示数值，对应元素表示当前下标大小数值的个数</span><br>        <span class="hljs-keyword">int</span>[] buckets = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[maxValue + <span class="hljs-number">1</span>];<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i : arr) &#123;<br>            buckets[i] ++;<br>        &#125;<br>        <span class="hljs-comment">//index表示arr的下标，用以排序</span><br>        <span class="hljs-keyword">int</span> index = <span class="hljs-number">0</span>;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; maxValue + <span class="hljs-number">1</span>; ++j) &#123;<br>            <span class="hljs-keyword">while</span> (buckets[j] &gt; <span class="hljs-number">0</span>) &#123;<br>                arr[index++] = j;<br>                -- buckets[j];<br>            &#125;<br>        &#125;<br>    &#125;<br><br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">int</span> <span class="hljs-title">getMaxValue</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] arr)</span> </span>&#123;<br>        <span class="hljs-keyword">int</span> max = arr[<span class="hljs-number">0</span>];<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt; arr.length; ++i) &#123;<br>            <span class="hljs-keyword">if</span> (max &lt; arr[i]) &#123;<br>                max = arr[i];<br>            &#125;<br>        &#125;<br>        <span class="hljs-keyword">return</span> max;<br>    &#125;<br>    <br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;<br>        <span class="hljs-keyword">int</span>[] arr = &#123;<span class="hljs-number">11</span>,<span class="hljs-number">44</span>,<span class="hljs-number">23</span>,<span class="hljs-number">67</span>,<span class="hljs-number">88</span>,<span class="hljs-number">65</span>,<span class="hljs-number">34</span>,<span class="hljs-number">48</span>,<span class="hljs-number">9</span>,<span class="hljs-number">12</span>&#125;;<br>        countingSort(arr, getMaxValue(arr));<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;arr.length;i++)&#123;<br>            System.out.print(arr[i]+<span class="hljs-string">&quot; &quot;</span>);<br>        &#125;<br>    &#125;<br><br>&#125;<br></code></pre></div></td></tr></table></figure>

<hr>
<h4 id="9-桶排序"><a href="#9-桶排序" class="headerlink" title="9.桶排序"></a>9.桶排序</h4><p>桶排序是计数排序的升级版，是一种近乎彻底<strong>分治思想</strong>。它利用了<strong>函数的映射关系</strong>，<strong>高效与否的关键就在于这个映射函数的确定</strong>。  </p>
<p>为了使桶排序更加高效，我们需要做到这两点：  </p>
<ol>
<li>在额外空间充足的情况下，尽量增大桶的数量</li>
<li>使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中</li>
</ol>
<p>同时，对于桶中元素的排序，<strong>选择何种比较排序算法对于性能的影响至关重要</strong>。</p>
<ol>
<li>什么时候最快：当输入的数据可以均匀的分配到每一个桶中。</li>
<li>什么时候最慢：当输入的数据被分配到了同一个桶中。</li>
</ol>
<p><img src="/images/pasted-66.png" srcset="/img/loading.gif" lazyload alt="upload successful"></p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">import</span> java.util.Arrays;<br><br><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">BucketSort</span> </span>&#123;<br><br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">bucketSort</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] arr)</span> </span>&#123;<br>        <span class="hljs-keyword">if</span> (arr.length &lt;= <span class="hljs-number">1</span>) &#123;<br>            <span class="hljs-keyword">return</span>;<br>        &#125;<br>        <span class="hljs-comment">//假设桶的容量为5</span><br>        <span class="hljs-keyword">int</span> bucketSize = <span class="hljs-number">5</span>;<br><br>        <span class="hljs-comment">//得到数组的最大、最小值（可以放在外部的方法里）</span><br>        <span class="hljs-keyword">int</span> min = arr[<span class="hljs-number">0</span>], max = arr[<span class="hljs-number">0</span>];<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt; arr.length; ++i) &#123;<br>            <span class="hljs-keyword">if</span> (min &gt; arr[i]) &#123;<br>                min = arr[i];<br>            &#125;<br>            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (max &lt; arr[i]) &#123;<br>                max = arr[i];<br>            &#125;<br>        &#125;<br><br>        <span class="hljs-comment">//桶的个数，防止(max - min) / bucketSize = 0，所以+1</span><br>        <span class="hljs-keyword">int</span> bucketNum = (max - min) / bucketSize + <span class="hljs-number">1</span>;<br>        <span class="hljs-keyword">int</span>[][] buckets = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[bucketNum][<span class="hljs-number">0</span>];<br><br>        <span class="hljs-comment">//利用函数映射将数据分配到桶中</span><br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; arr.length; ++i) &#123;<br>            <span class="hljs-keyword">int</span> index = (arr[i] - min) / bucketSize;<br>            <span class="hljs-comment">//需要的时候再扩容，节约空间</span><br>            buckets[index] = Arrays.copyOf(buckets[index], buckets[index].length + <span class="hljs-number">1</span>);<br>            buckets[index][buckets[index].length - <span class="hljs-number">1</span>] = arr[i];<br>        &#125;<br><br>        <span class="hljs-keyword">int</span> index = <span class="hljs-number">0</span>;<br>        <span class="hljs-comment">//对每个桶中的数据进行排序</span><br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span>[] bucket : buckets) &#123;<br>            <span class="hljs-keyword">if</span> (bucket.length &lt; <span class="hljs-number">1</span>) &#123;<br>                <span class="hljs-keyword">continue</span>;<br>            &#125;<br>            <span class="hljs-comment">//使用快排</span><br>            QuickSort.sort(bucket, <span class="hljs-number">0</span>, bucket.length - <span class="hljs-number">1</span>);<br>            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i : bucket) &#123;<br>                arr[index++] = i;<br>            &#125;<br>        &#125;<br><br>    &#125;<br>    <br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;<br>        <span class="hljs-keyword">int</span>[] arr = &#123;<span class="hljs-number">11</span>,<span class="hljs-number">44</span>,<span class="hljs-number">23</span>,<span class="hljs-number">67</span>,<span class="hljs-number">88</span>,<span class="hljs-number">65</span>,<span class="hljs-number">34</span>,<span class="hljs-number">48</span>,<span class="hljs-number">9</span>,<span class="hljs-number">12</span>&#125;;<br>        bucketSort(arr);<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;arr.length;i++)&#123;<br>            System.out.print(arr[i]+<span class="hljs-string">&quot; &quot;</span>);<br>        &#125;<br>    &#125;<br><br>&#125;<br></code></pre></div></td></tr></table></figure>

<hr>
<h4 id="10-基数排序"><a href="#10-基数排序" class="headerlink" title="10.基数排序"></a>10.基数排序</h4><p>基数排序是一种<strong>非比较型整数排序算法</strong>，其原理是<strong>将整数按位数切割成不同的数字，然后按每个位数分别比较</strong>。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也<strong>不是只能使用于整数</strong>。</p>
<div class="hljs code-wrapper"><pre><code class="hljs">上述三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：  
基数排序：根据键值的每位数字来分配桶；  
计数排序：每个桶只存储单一键值；  
桶排序：每个桶存储一定范围的数值。
</code></pre></div>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">import</span> java.util.Arrays;<br><br><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">RadixSort</span> </span>&#123;<br><br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">radixSort</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] arr)</span> </span>&#123;<br>        <span class="hljs-keyword">if</span> (arr.length &lt; <span class="hljs-number">2</span>) &#123;<br>            <span class="hljs-keyword">return</span>;<br>        &#125;<br>        <span class="hljs-comment">//获取arr数组中的最高位数，考虑负数所以用abs()</span><br>        <span class="hljs-keyword">int</span> max = Math.abs(arr[<span class="hljs-number">0</span>]);<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt; arr.length; ++i) &#123;<br>            <span class="hljs-keyword">if</span> (max &lt; Math.abs(arr[i])) &#123;<br>                max = Math.abs(arr[i]);<br>            &#125;<br>        &#125;<br>        <span class="hljs-keyword">int</span> max_length = <span class="hljs-number">1</span>;<br>        <span class="hljs-keyword">while</span> (max &gt;= <span class="hljs-number">10</span>) &#123;<br>            max /= <span class="hljs-number">10</span>;<br>            ++ max_length;<br>        &#125;<br><br>        <span class="hljs-keyword">int</span> mod = <span class="hljs-number">10</span>, dev = <span class="hljs-number">1</span>;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; max_length; ++i) &#123;<br>            <span class="hljs-comment">//考虑负数, 0-9对应负数，10-19对应正数：num % mod / dev + 10</span><br>            <span class="hljs-comment">//因为每次都是新的桶，要清空原来的数据，所以重新new</span><br>            <span class="hljs-keyword">int</span>[][] buckets = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[<span class="hljs-number">20</span>][<span class="hljs-number">0</span>];<br>            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> num : arr) &#123;<br>                <span class="hljs-keyword">int</span> index = num / dev % mod + <span class="hljs-number">10</span>;<br>                <span class="hljs-comment">//扩容buckets[index][]数组</span><br>                buckets[index] = Arrays.copyOf(buckets[index], buckets[index].length + <span class="hljs-number">1</span>);<br>                buckets[index][buckets[index].length - <span class="hljs-number">1</span>] = num;<br>            &#125;<br>            <span class="hljs-keyword">int</span> index = <span class="hljs-number">0</span>;<br>            <span class="hljs-comment">//按当前位上的数排序后放回数组中，准备更高位的排序</span><br>            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; <span class="hljs-number">20</span>; ++j) &#123;<br>                <span class="hljs-keyword">if</span> (buckets[j].length &gt; <span class="hljs-number">0</span>) &#123;<br>                    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> num : buckets[j]) &#123;<br>                        arr[index++] = num;<br>                    &#125;<br>                &#125;<br>            &#125;<br>            mod *= <span class="hljs-number">10</span>;<br>            dev *= <span class="hljs-number">10</span>;<br>        &#125;<br>    &#125;<br>    <br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;<br>        <span class="hljs-keyword">int</span>[] arr = &#123;<span class="hljs-number">11</span>,<span class="hljs-number">44</span>,-<span class="hljs-number">23</span>,<span class="hljs-number">67</span>,<span class="hljs-number">88</span>,<span class="hljs-number">65</span>,<span class="hljs-number">34</span>,<span class="hljs-number">48</span>,<span class="hljs-number">9</span>,-<span class="hljs-number">12</span>&#125;;<br>        radixSort(arr);<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;arr.length;i++)&#123;<br>            System.out.print(arr[i]+<span class="hljs-string">&quot; &quot;</span>);<br>        &#125;<br>    &#125;<br><br>&#125;<br></code></pre></div></td></tr></table></figure>

<hr>
<h3 id="算法题目"><a href="#算法题目" class="headerlink" title="算法题目"></a>算法题目</h3><p><strong>下文均为算法题的思路、解析等。</strong></p>
<h4 id="JZ51-数组中的逆序对-M"><a href="#JZ51-数组中的逆序对-M" class="headerlink" title="JZ51 数组中的逆序对 M"></a>JZ51 数组中的逆序对 M</h4><p>描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007。</p>
<p>解：使用归并排序，归并的过程中累加左右交换的次数。  </p>
<p><strong>注意：m + 1 - i 而非 j - i，因为 j 从 mid + 1 开始往后移动，当第一个 j 被移走之后，j + 1 此时就在 mid + 1 的位置，也就是 j 的位置。而 i 移动之后就是向后移动了。每次累加都要 % ，防止过程中count超出int限制。</strong></p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>&#123;<br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">InversePairs</span><span class="hljs-params">(<span class="hljs-keyword">int</span> [] array)</span> </span>&#123;<br>        temp = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[array.length];<br>        sort(array, <span class="hljs-number">0</span>, array.length - <span class="hljs-number">1</span>);<br>        <span class="hljs-keyword">return</span> count % <span class="hljs-number">1000000007</span>;<br>    &#125;<br>    <br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">sort</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] arr, <span class="hljs-keyword">int</span> left, <span class="hljs-keyword">int</span> right)</span> </span>&#123;<br>        <span class="hljs-keyword">if</span> (left &lt; right) &#123;<br>            <span class="hljs-keyword">int</span> mid = (left + right) / <span class="hljs-number">2</span>;<br>            sort(arr, left, mid);<br>            sort(arr, mid + <span class="hljs-number">1</span>, right);<br>            merge(arr, left, mid, right);<br>        &#125;<br>    &#125;<br>    <br>    <span class="hljs-keyword">static</span> <span class="hljs-keyword">int</span>[] temp;<br>    <span class="hljs-keyword">static</span> <span class="hljs-keyword">int</span> count = <span class="hljs-number">0</span>;<br>    <br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">merge</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] arr, <span class="hljs-keyword">int</span> l, <span class="hljs-keyword">int</span> m, <span class="hljs-keyword">int</span> r)</span> </span>&#123;<br>        <span class="hljs-keyword">int</span> i = l, j = m + <span class="hljs-number">1</span>, index = <span class="hljs-number">0</span>;<br>        <span class="hljs-keyword">while</span> (i &lt;= m &amp;&amp; j &lt;= r) &#123;<br>            <span class="hljs-keyword">if</span> (arr[i] &lt;= arr[j]) &#123;<br>                temp[index++] = arr[i++];<br>            &#125; <span class="hljs-keyword">else</span> &#123;<br>                <span class="hljs-comment">//m + 1 - i而非j - i；此处就要%，防止过程中count超出int限制</span><br>                count = (count + m + <span class="hljs-number">1</span> - i) % <span class="hljs-number">1000000007</span>;<br>                temp[index++] = arr[j++];<br>            &#125;<br>        &#125;<br>        <span class="hljs-keyword">while</span> (i &lt;= m) &#123;<br>            temp[index++] = arr[i++];<br>        &#125;<br>        <span class="hljs-keyword">while</span> (j &lt;= r) &#123;<br>            temp[index++] = arr[j++];<br>        &#125;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> k = <span class="hljs-number">0</span>; k &lt; index; ++k) &#123;<br>            arr[k + l] = temp[k];<br>        &#125;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>

<hr>
<h4 id=""><a href="#" class="headerlink" title=""></a></h4>
            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>
                    
                  </div>
                
                
                  <div class="post-meta">
                    <i class="iconfont icon-tags"></i>
                    
                      <a class="hover-with-bg" href="/tags/%E6%8E%92%E5%BA%8F/">排序</a>
                    
                  </div>
                
              </div>
              
                <p class="note note-warning">
                  
                    本博客所有文章未经允许，严禁转载！
                  
                </p>
              
              
                <div class="post-prevnext">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/2022/03/31/%E5%9F%BA%E7%A1%80-Java/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">Java基础&容器-Java</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/2022/03/24/%E7%AE%97%E6%B3%95--%E5%9B%9E%E6%BA%AF/">
                        <span class="hidden-mobile">算法---回溯</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div class="toc-body" id="toc-body"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    

    
      <a id="scroll-top-button" aria-label="TOP" href="#" role="button">
        <i class="iconfont icon-arrowup" aria-hidden="true"></i>
      </a>
    

    
      <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
    

    
  </main>

  <footer class="text-center mt-5 py-3">
  <div class="footer-content">
     CC <i class="iconfont icon-love"></i> XX
  </div>
  
  <div class="statistics">
    
    

    
      
        <!-- 不蒜子统计PV -->
        <span id="busuanzi_container_site_pv" style="display: none">
            总访问量 
            <span id="busuanzi_value_site_pv"></span>
             次
          </span>
      
      
        <!-- 不蒜子统计UV -->
        <span id="busuanzi_container_site_uv" style="display: none">
            总访客数 
            <span id="busuanzi_value_site_uv"></span>
             人
          </span>
      
    
  </div>


  

  
</footer>


  <!-- SCRIPTS -->
  
  <script  src="https://cdn.jsdelivr.net/npm/nprogress@0/nprogress.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/nprogress@0/nprogress.min.css" />

  <script>
    NProgress.configure({"showSpinner":false,"trickleSpeed":100})
    NProgress.start()
    window.addEventListener('load', function() {
      NProgress.done();
    })
  </script>


<script  src="https://cdn.jsdelivr.net/npm/jquery@3/dist/jquery.min.js" ></script>
<script  src="https://cdn.jsdelivr.net/npm/bootstrap@4/dist/js/bootstrap.min.js" ></script>
<script  src="/js/events.js" ></script>
<script  src="/js/plugins.js" ></script>

<!-- Plugins -->


  <script  src="/js/local-search.js" ></script>



  
    
      <script  src="/js/img-lazyload.js" ></script>
    
  



  



  
    <script  src="https://cdn.jsdelivr.net/npm/tocbot@4/dist/tocbot.min.js" ></script>
  
  
    <script  src="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3/dist/jquery.fancybox.min.js" ></script>
  
  
    <script  src="https://cdn.jsdelivr.net/npm/anchor-js@4/anchor.min.js" ></script>
  
  
    <script defer src="https://cdn.jsdelivr.net/npm/clipboard@2/dist/clipboard.min.js" ></script>
  



  <script defer src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>




  <script  src="https://cdn.jsdelivr.net/npm/typed.js@2/lib/typed.min.js" ></script>
  <script>
    (function (window, document) {
      var typing = Fluid.plugins.typing;
      var title = document.getElementById('subtitle').title;
      
        typing(title);
      
    })(window, document);
  </script>















<!-- 主题的启动项 保持在最底部 -->
<script  src="/js/boot.js" ></script>


</body>
</html>
